package leetcode_1_200;

import java.util.LinkedList;
import java.util.Stack;

public class LeeCode_32 {
    public static void main(String[] args) {
        System.out.println(longestValidParentheses2("(()"));
        System.out.println(longestValidParentheses2(")()())"));
        System.out.println(longestValidParentheses2(""));
    }
    private static int longestValidParentheses2(String s) {
        int n = s.length();
        char[] chars = s.toCharArray();
        int i = 0;
        LinkedList<Integer> list = new LinkedList<>();
        for (int j = 0; j < n; j++) {
            list.add(j);
        }
        while (i < list.size() - 1){
            int next = list.get(i + 1), now = list.get(i);
            if (chars[now] == '(' && chars[next] == ')'){
                chars[now] = '1';
                chars[next] = '1';
                list.remove(i);
                list.remove(i);
                i--;
                i = Math.max(i, 0);
            }else {
                i++;
            }
        }
        int j = 0, ans = 0, count = 0;
        while (j < n){
            if (chars[j] == '1'){
                count++;
            }else {
                ans = Math.max(ans, count);
                count = 0;
            }
            j++;
        }
        return Math.max(ans, count);
    }
    private static int longestValidParentheses(String s) {
        int n = s.length(), ans = 0;
        for (int i = 0; i < n; i++) {
            int cl = 0, cr = 0, index = i, count = 0;
            Stack<Character> stack = new Stack<>();
            while (index < n){
                if (stack.isEmpty()){
                    ans = Math.max(ans, count);
                    stack.add(s.charAt(index));
                }else {
                    if (s.charAt(index) == '('){
                        stack.add('(');
                    }else {
                        Character pop = stack.pop();
                        if (pop == ')'){
                            break;
                        }
                    }
                }
                cl += s.charAt(index) == '(' ? 1 : 0;
                cr += s.charAt(index) == ')' ? 1 : 0;
                if (cr > cl)
                    break;
                count++;
                index++;
            }
            if (stack.isEmpty() && cl == cr){
                ans = Math.max(ans, count);
            }
        }
        return ans;
    }
}
